//给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[
//i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为
// 1 ，1 表示节点 i 处有一个金币。 
//
// 一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次： 
//
// 
// 收集距离当前节点距离为 2 以内的所有金币，或者 
// 移动到树中一个相邻节点。 
// 
//
// 你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。 
//
// 如果你多次经过一条边，每一次经过都会给答案加一。 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
//输出：2
//解释：从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2 。
// 
//
// 示例 2： 
//
// 
//
// 输入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5
//,7]]
//输出：2
//解释：从节点 0 出发，收集节点 4 和 3 处的金币，移动到节点 2 处，收集节点 7 处的金币，移动回节点 0 。
// 
//
// 
//
// 提示： 
//
// 
// n == coins.length 
// 1 <= n <= 3 * 10⁴ 
// 0 <= coins[i] <= 1 
// edges.length == n - 1 
// edges[i].length == 2 
// 0 <= ai, bi < n 
// ai != bi 
// edges 表示一棵合法的树。 
// 
//
// Related Topics 树 图 拓扑排序 数组 👍 67 👎 0


package LeetCode.editor.cn;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ldltd
 * @date 2023-09-21 10:01:14
 * @description 2603.收集树中金币
 */
public class CollectCoinsInATree{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new CollectCoinsInATree().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*
		 * 1,首先读入图，计算每个节点的度数
		 * 2，删除没有金币的叶子节点（用队列实现）
		 * 3，删除到父节点的边，剩余节点就是必须要访问的节点
		 * 4，最后所有需要走的点，因为要回到原点，所以每条边都至少访问两边
		 * 5，如果所有点都被删除，当只剩下两个点时，这两个点的边会被删除两次=-1
		 * 	所以答案在-1和0直接取最大值
		 * */
    public int collectTheCoins(int[] coins, int[][] edges) {
		int n = coins.length;
		List<Integer>[] g =new ArrayList[n];
		Arrays.setAll(g,e->new ArrayList<>());
		var deg=new int[n];
		for (int[] edge : edges) {
			int x=edge[0],y=edge[1];
			//建图
			g[x].add(y);
			g[y].add(x);
			//统计每个点的度数
			deg[x]++;
			deg[y]++;
		}
		//剩余的边数
		int leftEdges=n-1;
		//拓扑排序，去掉没有金币的叶子节点
		var q=new ArrayDeque<Integer>();
		for (int i = 0; i < n; i++) {
			if(deg[i]==1&&coins[i]==0){
				q.add(i);
			}
		}
		while (!q.isEmpty()){
			leftEdges--;//删除节点到父节点的边
			for (Integer y : g[q.poll()]) {
				if(--deg[y]==1&&coins[y]==0){//删除后，末节点如果又变成没有金币的叶子继续加入
					q.add(y);
				}
			}
		}

		//再次拓扑排序
		for (int i = 0; i < n; i++) {
			// 有金币的叶子（判断 coins[i] 是避免把没有金币的叶子也算进来）
			if(deg[i]==1&&coins[i]==1){
				q.add(i);
			}
		}
		leftEdges-= q.size();//删除所有叶子（到其父节点的边）
		for (Integer x : q) {
			for (Integer y : g[x]) {
				if(--deg[y]==1){ //y现在是叶子节点了
					leftEdges--;
				}
			}
		}
		return  Math.max(leftEdges*2,0);
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
